/*
	Copyright (c) 2009, SpLib.net
  	All rights reserved.
  	
  	Author:6spring
  	About:map，二分法查找
*/

package SpLib.std
{
	import SpLib.std.iterator;
	
	public class map
	{	
		private var m_szNodeList:Array = new Array;
		private var m_nSize:int = 0;
		private var m_CompareFunc:Function = null;
		
		public function map(func:Function = null)
		{
			m_CompareFunc = func;
		}

		public function size():int
		{
			return m_nSize;
		} 
		
		public function empty():Boolean
		{
			return m_nSize==0;
		}
		
		public function clear():void
		{
			for each (var item:iterator in m_szNodeList)
			{
				item.release();
			}

			m_szNodeList.length = 0;
			m_nSize = 0;
		}
		
		public function begin():iterator
		{
			return m_nSize>0?m_szNodeList[0]:null;
		}
		
		public function end():iterator
		{
			return null;
		}
		
		public function find(key:*):iterator
		{
			if(m_nSize==0)
			{
				return null;
			}

			var beg:int = 0;
			var end:int = m_nSize-1;
			var mid:int = 0;
			var miditer:iterator;
			
			if(m_CompareFunc!=null)
			{
				while(beg<=end)
				{
					mid = (beg+end)/2;
					miditer = m_szNodeList[mid];
										
					switch(m_CompareFunc(miditer.m_Key,key))
					{
					case 0:
						return miditer;
					break;
					case 1:
						end = mid - 1;
					break;
					case -1:
						beg = mid + 1;
					break;
					}
				}
			}
			else
			{
				var keyval:uint = SpLib.std.utils.GetKey_Hash(key);
				var midkeyval:uint;
				while(beg<=end)
				{
					mid = (beg+end)/2;
					miditer = m_szNodeList[mid];
					midkeyval = SpLib.std.utils.GetKey_Hash(miditer.m_Key);
					
					if(midkeyval==keyval)
					{
						return miditer;
					}
					
					if(midkeyval>keyval)
					{
						end = mid - 1;
					}
					else
					{
						beg = mid + 1;
					}
				}
			}
					
			return null;
		}

		public function insert(key:*,data:*):Boolean
		{
			var beg:int = 0;
			var end:int = m_nSize-1;
			var mid:int = 0;
			var miditer:iterator;
			var node:iterator = new iterator(data,key);
			
			if(m_nSize==0)
			{
				++m_nSize;
				m_szNodeList.push(node);
				return true;
			}
			
			if(m_CompareFunc!=null)
			{
				while(beg<=end)
				{
					mid = (beg+end)/2;
					miditer = m_szNodeList[mid];
										
					switch(m_CompareFunc(miditer.m_Key,key))
					{
					case 0:
						return false;
					break;
					case 1:
						end = mid - 1;
					break;
					case -1:
						beg = mid + 1;
					break;
					}
				}
			}
			else
			{
				var keyval:uint = SpLib.std.utils.GetKey_Hash(key);
				var midkeyval:uint;
				while(beg<=end)
				{
					mid = (beg+end)/2;
					miditer = m_szNodeList[mid];
					midkeyval = SpLib.std.utils.GetKey_Hash(miditer.m_Key);
					
					if(midkeyval==keyval)
					{
						return false;
					}
					
					if(midkeyval>keyval)
					{
						end = mid - 1;
					}
					else
					{
						beg = mid + 1;
					}
				}
			}
	
			var offset:iterator;
			if(m_nSize>beg)
			{
				offset = m_szNodeList[beg] as iterator;
				offset.prev = node;
				m_szNodeList.splice(beg,0,node);
			}
			else
			{
				offset = m_szNodeList[m_szNodeList.length-1] as iterator;
				offset.next = node;
				m_szNodeList.push(node);
			}
					
			++m_nSize;
			
			return true;
		}
		
		public function erase(iter:iterator):iterator
		{
			if(iter==null) return null;
			
			var i:int;
			for(i=0;i<m_nSize;i++)
			{
				if(iter==m_szNodeList[i])
				{
					iter.release();
					m_szNodeList.splice(i,1);
					--m_nSize;
					
					return m_nSize==0?null:m_szNodeList[i];
				}
			}

			return null;		
		}
		
		public function setvalue(key:*,data:*):void
		{
			var iter:iterator = find(key);
			if(iter==null)
			{
				insert(key,data);	
			}
			else
			{
				iter.m_Data = data;
			}
		}
		
		public function remove(key:*):void
		{
			erase(find(key));
		}
	}
}